package algorithmcase;

import java.util.ArrayList;
import java.util.Arrays;

//分块查找
public class Case2 {
    public static void main(String[] args) {
        int[] arr = {7,13,12,16,17,23,26,33,47,51,63,77,89,91,94,96};
//        Block b1 = new Block(16,0,3);
//        Block b2 = new Block(33,4,7);
//        Block b3 = new Block(77,8,11);
//        Block b4 = new Block(94,12,15);
//        ArrayList<Block> blockList = getBlockList(arr);
//        for (int i = 0; i < blockList.size(); i++) {
//            System.out.println(blockList.get(i).getMax());
//            System.out.println(blockList.get(i).getStartIndex());
//            System.out.println(blockList.get(i).getEndIndex());
//        }
        int targetIndex = findIndexInBlock(arr,96);
        System.out.println(targetIndex);
    }
    //将目标数据转换为块索引
    public static ArrayList<Block> getBlockList(int[] arr){
        ArrayList<Block> blockList = new ArrayList<Block>();
        //创建一个 int 变量存储开根号长度，不能整除时向上取整
        int len = (int) Math.ceil(Math.sqrt(arr.length));
        System.out.println(len);
        for (int i = 0; i < len; i++) {
            //截取结束角标
            int endMark = Math.min(i*len+len,arr.length);
            //创建一个 Block 对象，存储当前块的最大值、开始索引、结束索引
            Block block = new Block();
            //创建一个新数组，截取当前块的元素copyOfRange包含开头，不包含结尾
            int[] subArr = Arrays.copyOfRange(arr,i*len,endMark);
            // 计算子数组的最大值
            int subArrMax = subArr[0];
            for (int num : subArr) {
                if (num > subArrMax) {
                    subArrMax = num;
                }
            }
            //设置最大值
            block.setMax(subArrMax);
            //设置开始索引
            block.setStartIndex(i*len);
            //设置结束索引
            block.setEndIndex(endMark-1);
            blockList.add(block);
        }
        return blockList;
    }

    //在块列表中查找目标数据所在的块索引
    public static int findBlockIndexInList(ArrayList<Block> blockList,int target) {
        for (int i = 0; i < blockList.size(); i++) {
            if (target <= blockList.get(i).getMax()) {
                return i;
            }
        }
        return -1;
    }
    //在目标区域查询目标数据的索引
    public static int findIndexInBlock(int[] arr,int target) {
        ArrayList<Block> blockList = getBlockList(arr);
        int targetBlockIndex = findBlockIndexInList(blockList, target);
        if (targetBlockIndex == -1) {
            return -1;
        }
        Block block = blockList.get(targetBlockIndex);
        //在目标区域查询目标数据的索引
        for (int i = block.getStartIndex(); i <= block.getEndIndex(); i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

}
